package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;

/**
 * (B卷,100分)- 最长连续子序列（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 有N个正整数组成的一个序列。给定整数sum，求长度最长的连续子序列，使他们的和等于sum，返回此子序列的长度，
 * <p>
 * 如果没有满足要求的序列，返回-1。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入是：N个正整数组成的一个序列
 * <p>
 * 第二行输入是：给定整数sum
 * <p>
 * 输出描述
 * <p>
 * 最长的连续子序列的长度
 * <p>
 * 备注
 * 输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔
 * 序列长度：1 <= N <= 200
 * 输入序列不考虑异常情况
 * <p>
 * 用例
 * <p>
 * 输入
 * 1,2,3,4,2
 * 6
 * <p>
 * 输出	3
 * 说明	1,2,3和4,2两个序列均能满足要求，所以最长的连续序列为1,2,3，因此结果为3。
 * <p>
 * 输入	1,2,3,4,2
 * 20
 * 输出	-1
 * 说明	没有满足要求的子序列，返回-1
 * <p>
 * 前缀和解法
 * <p>
 * 本题数量级不大，可以考虑求解输入序列的前缀和数组，实现O(1)时间复杂度计算任意区间和
 */
public class LongestTargetSubstring {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int target = Integer.parseInt(sc.nextLine());*/

        int[] nums = Arrays.stream("1 2 3 4 2".split(" ")).mapToInt(Integer::parseInt).toArray();
        int target = 6;

        System.out.println(getResult(nums, target));
    }

    /**
     * 前缀和（完美解决负数的情况）
     *
     * @param nums
     * @param target
     * @return
     */
    public static int getResult(int[] nums, int target) {
        int n = nums.length;

        // 前缀和数组
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        // 记录最长连续子序列的长度
        int maxLen = -1;

        // 求解所有连续子序列的区间和
        for (int l = 0; l <= n - 1; l++) { // L R 前闭后开
            for (int r = l + 1; r <= n; r++) {
                if (preSum[r] - preSum[l] == target) {
                    maxLen = Math.max(maxLen, r - l);
                }
            }
        }

        return maxLen;
    }

    /**
     * 滑动窗口（不能解决负数的情况）
     *
     * @param nums
     * @param target
     * @return
     */
    public static int getResult2(int[] nums, int target) {

        int n = nums.length;

        int maxLen = -1;

        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            if (target < sum) {
                continue;
            }
            if (target == sum) {
                maxLen = Integer.max(maxLen, 1);
                break;
            }
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                sum += nums[j];
                count++;
                if (sum > target) {
                    break;
                }
                if (sum == target) {
                    maxLen = Integer.max(maxLen, count);
                    break;
                }
            }
        }

        return maxLen;
    }
}
